package gsw.tool.datastructure.tree;

/**
 * AVL树：一种每一个节点的左子树与右子树的高度差最多等于1的自平衡二叉查找树。
 *
 * @param <E>
 */
public class TreeAVL<E extends Comparable> extends TreeBinarySearch<E> {
    final int RH = -1;
    final int LH = 1;
    final int EH = 0;

    public static void test() {
        TreeAVL tree = new TreeAVL();
        tree.createData();
        tree.recursionPre();
    }

    /**
     * 添加AVL树节点。
     * 记添加节点的父节点为A,最小不平衡节点为B.
     * 1.当A不是叶子节点时，平衡无影响；
     * 2.当A是叶子节时，同向单旋，异向双旋：
     * a.LL:B的左子树高，添加节点位于B的左子树的左子树，对B右旋；
     * b.LR:B的左子树高，添加节点位于B的左子树的右子树，先对B的左节点左旋，在对B右旋；
     * c.RR:B的右子树高，添加节点位于B的左子树的右子树，对B左旋；
     * d.RL:B的右子树高，添加节点位于B的左子树的左子树，先对B的左节点右旋，对B左旋；
     *
     * @param data
     */
    @Override
    public void put(E data) {
        Node<E> now = new Node<E>(data);
        if (root == null) {
            root = now;
            return;
        }

        Node<E> parent = root;
        // 添加:像二叉查找树一样添加
        while (parent != null) {
            if (data.compareTo(parent.data) < 0) {
                if (parent.left == null) {
                    parent.left = now;
                    now.parent = parent;
                    break;
                } else {
                    parent = parent.left;
                }
            } else if (data.compareTo(parent.data) > 0) {
                if (parent.right == null) {
                    parent.right = now;
                    now.parent = parent;
                    break;
                } else {
                    parent = parent.right;
                }
            } else {
                return;
            }
        }

        // 检查平衡，修正位置
        while (parent != null) {
            // 如果新增节点是左子节点，则其父节点的平衡因子+1
            if (data.compareTo(parent.data) < 0) {
                parent.bran++;
                // 如果新增节点是右子节点，则其父节点的平衡因子-1
            } else {
                parent.bran--;
            }

            if (parent.bran == 0) {
                break;
            } else if (Math.abs(parent.bran) == 2) {
                // 出现平衡问题
                fixAfterInsertion(parent);
                break;
            } else {
                parent = parent.parent;
            }
        }
    }

    /**
     * 修正位置
     *
     * @param parent
     */
    private void fixAfterInsertion(Node<E> parent) {
        if (parent.bran == 2) {
            leftBranch(parent);
        }
        if (parent.bran == -2) {
            rightBranch(parent);
        }
    }

    /**
     * 左旋：把节点向左下移一位
     *
     * @param node
     */
    public void leftRoate(Node<E> node) {
        if (node == null) {
            return;
        }

        Node<E> right = node.right;
        // 1.把node的右子节点的左节点变成node的右子节点
        node.right = right.left;
        if (right.left != null) {
            right.left.parent = node;
        }

        // 2.把node的右子节点变出node的父节点的子节点
        right.parent = node.parent;
        if (node.parent == null) {
            root = right;
        } else if (node.parent.right == node) {
            node.parent.right = right;
        } else if (node.parent.left == node) {
            node.parent.left = right;
        }

        // 3.把node变成node的右子节点的左子节点
        right.left = node;
        node.parent = right;
    }

    /**
     * 右旋：把节点向右下移一位
     *
     * @param node
     */
    public void rightRoate(Node<E> node) {
        if (node == null) {
            return;
        }

        Node<E> left = node.left;
        // 1.把node的左子节点的右节点变成node的左子节点
        node.left = left.right;
        if (left.right != null) {
            left.right.parent = node;
        }

        // 2.把node的左子节点变出node的父节点的子节点
        left.parent = node.parent;
        if (node.parent == null) {
            root = left;
        } else if (node.parent.left == node) {
            node.parent.left = left;
        } else if (node.parent.right == node) {
            node.parent.right = left;
        }

        // 3.把node变成node的左子节点的右子节点
        left.right = node;
        node.parent = left;
    }

    /**
     * 对左子树操作
     *
     * @param node
     */
    public void leftBranch(Node<E> node) {
        if (node == null) {
            return;
        }

        Node<E> left = node.left;
        //单向右旋
        if (left.bran == LH) {
            rightRoate(node);
            //平衡因子都变成0
            node.bran = EH;
            left.bran = EH;

            //先左旋，再右旋。
        } else if (left.bran == RH) {
            Node<E> lr = left.right;
            leftRoate(left);
            rightRoate(node);
            //2次旋转后，left变出lr的左子节点，node变出lr的右子节点
            if (lr.bran == LH) {
                node.bran = RH;
                left.bran = EH;
                lr.bran = EH;
            } else if (lr.bran == RH) {
                node.bran = EH;
                left.bran = LH;
                lr.bran = EH;
                // lr为叶子节点时
            } else if (lr.bran == EH) {
                node.bran = EH;
                left.bran = EH;
                lr.bran = EH;
            }
        }
    }

    /**
     * 对右子树操作
     *
     * @param node
     */
    public void rightBranch(Node<E> node) {
        if (node == null) {
            return;
        }

        Node<E> right = node.right;
        //单向左旋
        if (right.bran == RH) {
            leftRoate(node);
            //平衡因子都变成0
            node.bran = EH;
            right.bran = EH;
            //先右旋，再左旋。
        } else if (right.bran == LH) {
            Node<E> rl = right.left;
            rightRoate(right);
            leftRoate(node);
            //2次旋转后，right变出rl的右子节点，node变出rl的左子节点
            if (rl.bran == LH) {
                node.bran = EH;
                right.bran = RH;
                rl.bran = EH;
            } else if (rl.bran == RH) {
                node.bran = LH;
                right.bran = EH;
                rl.bran = EH;
                // rl为叶子节点时
            } else if (rl.bran == EH) {
                node.bran = EH;
                right.bran = EH;
                rl.bran = EH;
            }
        }
    }

    /**
     * 删除元素
     * TODO：待实现
     *
     * @param data
     * @return
     */
    @Override
    public Node<E> remove(E data) {
        super.remove(data);
        return null;
    }
}
